A path is a sequence of vertices $ (v_1, v_2, \dots, v_k) $ where each adjacent pair is connected by an edge $ (v_i, v_{i+1}) $ in $ E $.

  • In simple terms, a path is a way to "walk" from a starting node to an ending node by only following valid, existing edges.
  • For directed graphs, you must strictly follow the direction of the arrow defined by the edge.
  • Example Path: In the visualization, the sequence (A, B, D) is a valid path, as all edges exist in the specified direction.
  • Invalid Path: The sequence (A, C, B) is not valid, because the edge from C back to B, $(C, B)$, does not exist.

Formal Definition: Path

$$ \begin{aligned} &\text{1. Path Length Condition: } k \ge 2 \\ &\text{2. Edge Existence: For all } i \in \{1, \dots, k-1\}, \text{ the edge } (v_i, v_{i+1}) \in E. \end{aligned} $$